package com.aqie.medium.dynamicProgram;

/**
 * 5 最长回文子串
 */
public class LongestPalindrome {
    /**
     * 1, 中心扩展算法 O(n^2)
     * @param s
     * @return
     */
    public String longestPalindrome(String s) {
        if (s == null || s.length() < 1) return "";
        int start = 0, end = 0;
        for (int i = 0; i < s.length(); i++) {
            int len1 = expandAroundCenter(s, i, i);
            int len2 = expandAroundCenter(s, i, i + 1);
            int len = Math.max(len1, len2);
            if (len > end - start) {
                start = i - (len - 1) / 2;
                end = i + len / 2;
            }
        }
        return s.substring(start, end + 1);
    }

    private int expandAroundCenter(String s, int left, int right) {
        int L = left, R = right;
        while (L >= 0 && R < s.length() && s.charAt(L) == s.charAt(R)) {
            L--;
            R++;
        }
        return R - L - 1;
    }


    /**
     * 2, 马拉车算法 105ms
     */
    public String preProcess(String s) {
        int n = s.length();
        if (n == 0) {
            return "^$";
        }
        String ret = "^";
        for (int i = 0; i < n; i++)
            ret += "#" + s.charAt(i);
        ret += "#$";
        return ret;
    }
    public String longestPalindrome2(String s) {
        String T = preProcess(s);
        int n = T.length();
        int[] P = new int[n];
        int C = 0, R = 0;
        for (int i = 1; i < n - 1; i++) {
            int i_mirror = 2 * C - i;
            if (R > i) {
                P[i] = Math.min(R - i, P[i_mirror]);// 防止超出 R
            } else {
                P[i] = 0;// 等于 R 的情况
            }

            // 碰到之前讲的三种情况时候，需要利用中心扩展法
            while (T.charAt(i + 1 + P[i]) == T.charAt(i - 1 - P[i])) {
                P[i]++;
            }

            // 判断是否需要更新 R
            if (i + P[i] > R) {
                C = i;
                R = i + P[i];
            }

        }

        // 找出 P 的最大值
        int maxLen = 0;
        int centerIndex = 0;
        for (int i = 1; i < n - 1; i++) {
            if (P[i] > maxLen) {
                maxLen = P[i];
                centerIndex = i;
            }
        }
        int start = (centerIndex - maxLen) / 2; //最开始讲的求原字符串下标
        return s.substring(start, start + maxLen);
    }


    /**
     * 3, 暴力方法破解
     * @param s
     * @return
     */
    public String longestPalindrome3(String s) {
        int n = s.length();
        String res = "";
        boolean[] P = new boolean[n];
        for (int i = n - 1; i >= 0; i--) {
            for (int j = n - 1; j >= i; j--) {
                P[j] = s.charAt(i) == s.charAt(j) && (j - i < 3 || P[j - 1]);
                if (P[j] && j - i + 1 > res.length()) {
                    res = s.substring(i, j + 1);
                }
            }
        }
        return res;
    }

    /**
     * 4,DP
     * 申请一个二维的数组初始化为 0，然后判断对应的字符是否相等，相等的话
     * arr [ i ][ j ] = arr [ i - 1 ][ j - 1] + 1 。
     * 当 i = 0 或者 j = 0 的时候单独分析，字符相等的话 arr [ i ][ j ] 就赋为 1 。
     * arr [ i ][ j ] 保存的就是公共子串的长度。
     * @param s
     * @return
     */
    public String longestPalindrome4(String s) {
        if (s.equals(""))
            return "";
        String origin = s;
        String reverse = new StringBuffer(s).reverse().toString(); //字符串倒置
        int length = s.length();
        int[][] arr = new int[length][length];
        int maxLen = 0;
        int maxEnd = 0;
        for (int i = 0; i < length; i++) {
            for (int j = 0; j < length; j++) {
                if (origin.charAt(i) == reverse.charAt(j)) {
                    if (i == 0 || j == 0) {
                        arr[i][j] = 1;
                    } else {
                        arr[i][j] = arr[i - 1][j - 1] + 1;
                    }
                }
                if (arr[i][j] > maxLen) {
                    maxLen = arr[i][j];
                    maxEnd = i; //以 i 位置结尾的字符
                }

            }
        }
        return s.substring(maxEnd - maxLen + 1, maxEnd + 1);
    }

    /**
     *
     * @param s
     * @return
     */
    static boolean checkPalindrome(String s, int i, int j) {
        if (j>s.length()) return false;
        while (i<j) {
            if (s.charAt(i) != s.charAt(j)) {
                return false;
            }
            i++;
            j--;
        }
        return true;
    }


    /**
     * 5， 二分查找法  todo
     * a, s.substr(0,5);     //获得字符串s中从第0位开始的长度为5的字符串
     * b,
     * @param s
     * @return
     */
    public static String longestPalindrome5(String s) {
        int low = 0, high = s.length(), mid;
        String ans = "";
        if (s.equals("") || s.length() == 1)
            return s;

        while (low<=high) {
            mid = (low+high)/2;
            boolean changed = false;
            for (int i=0;i<s.length()-mid;i++) {
                if (checkPalindrome(s, i, i+mid-1)){
                    changed = true;
                    ans = s.substring(i, mid);
                    break;
                }
            }
            for (int i=0;i<s.length()-mid;i++) {  //此处应该-1，但最长时，会得到-1，因此在check函数里判断
                if (checkPalindrome(s, i, i+mid)){
                    changed = true;
                    ans = s.substring(i, mid+1);
                    break;
                }
            }

            if (!changed) {
                high = mid - 1;
            } else {
                low = mid + 1;
            }

        }
        return ans;
    }


    public static void main(String[] args) {
        String s = "abcdbbfcba";
        System.out.println(longestPalindrome5(s));
    }
}
